import java.util.ArrayList;
import java.util.List;

/**
 * @author shuang
 * @date 2022/5/1 19:07
 * 1305. 两棵二叉搜索树中的所有元素
 * https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/
 */
public class Solutions_1305 {
    public static void main(String[] args) {
//        String root1 = "[2 1 4]";
//        String root2 = "[1 0 3]";  // output: {0, 1, 1, 2, 3, 4}

        String root1 = "[1 # 8]";
        String root2 = "[8 1]";  // output: {1, 1, 8, 8}

        TreeNode treeNode1 = MyTreeNodeUtils.deserialize(root1);
        TreeNode treeNode2 = MyTreeNodeUtils.deserialize(root2);

        List<Integer> res = getAllElements(treeNode1, treeNode2);
        System.out.println(res);
    }

    public static List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> tree1Nums = getTreeElements(new ArrayList<>(), root1);
        List<Integer> tree2Nums = getTreeElements(new ArrayList<>(), root2);
        if (tree1Nums.size() == 0) {
            return tree2Nums;
        }
        if (tree2Nums.size() == 0) {
            return tree1Nums;
        }
        List<Integer> res = mergeTwoList(tree1Nums, tree2Nums);
        return res;
    }

    /**
     * 对两个列表进行排序
     * @param list1
     * @param list2
     * @return
     */
    public static List<Integer> mergeTwoList(List<Integer> list1, List<Integer> list2) {
        List<Integer> res = new ArrayList<>(list1.size() + list2.size());
        int i = 0, j = 0;
        for (; i < list1.size() && j < list2.size(); ) {
            Integer n1 = list1.get(i);
            Integer n2 = list2.get(j);
            if (n1 < n2) {
                res.add(n1);
                i ++;
            } else {
                res.add(n2);
                j ++;
            }
        }
        while (i < list1.size()) {
            res.add(list1.get(i));
            i ++;
        }
        while (j < list2.size()) {
            res.add(list2.get(j));
            j ++;
        }
        return res;
    }

    /**
     * 中序遍历完成树元素的添加
     * @param list
     * @param root
     * @return
     */
    public static List<Integer> getTreeElements(List<Integer> list, TreeNode root) {
        if (root == null) {
            return list;
        }
        getTreeElements(list, root.left);
        list.add(root.val);
        getTreeElements(list, root.right);
        return list;
    }
}

